package medium;

import java.text.Collator;
import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/9/26 19:28
 */
public class No39_组合总和 {
    public static void main(String[] args) {
        Solution39 solution39 = new Solution39();
        int[] candidates = new int[]{1, 2};
        List<List<Integer>> lists = solution39.combinationSum(candidates, 4);
        System.out.println(lists);
    }
}

class Solution39 {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //剪枝优化
        List<Integer> data = new ArrayList<>();
        combinationSum(candidates, 0, target, data);
        return res;
    }

    public void combinationSum(int[] candidates, int sum, int target, List<Integer> data) {
        
        if (sum == target) {
            //处理add
            List<Integer> dataCopy = new ArrayList<>(data);
            res.add(dataCopy);
            return;
        }else if (sum > target) {
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            //优化:剪枝操作
            //data.get(data.size()-1) data最后一个元素
            if (data.size() != 0 && data.get(data.size() - 1) < candidates[i]) {
                //说明非升序(降序)
                continue;
            } else {
                sum += candidates[i];
                data.add(candidates[i]);
                combinationSum(candidates, sum, target, data);
                //回溯
                sum -= candidates[i];
                data.remove(data.size() - 1);
            }
        }
    }
}



    ////全局变量
    //List<List<Integer>> res = new ArrayList<>();
    ////使用set暴力去重
    //Set<String> set = new HashSet<>();
    //
    //public List<List<Integer>> combinationSum(int[] candidates, int target) {
    //    //万物真理----->暴力法!!!
    //    //疯狂递归
    //    List<Integer> data = new ArrayList<>();
    //    combinationSum(candidates, 0, target, data);
    //    return res;
    //}
    //
    //
    ////sum:递归过程中求和
    ////target:目标值
    ////data:满足目标值的集合
    //public void combinationSum(int[] candidates, int sum, int target, List<Integer> data) {
    //    
    //    //递归终止条件
    //    //1.条件sum>target,终止
    //    //2.满足条件终止
    //    
    //    if (sum == target) {
    //        //考虑值传递问题,因此new一个
    //        //可以扔
    //        List<Integer> dataCopy = new ArrayList<>(data);
    //        //首先排序处理去重问题
    //        sortList(dataCopy);
    //        String base = "";
    //        for (int s : dataCopy) {
    //            base += s + "_";
    //        }
    //        if (set.add(base)) {
    //            res.add(dataCopy);
    //        }
    //        return;
    //    } else if (sum > target) {
    //        return;
    //    }
    //    
    //    for (int i = 0; i < candidates.length; i++) {
    //        sum += candidates[i];
    //        data.add(candidates[i]);
    //        combinationSum(candidates, sum, target, data);
    //        //注意回溯,不然大型bug!!!
    //        sum -= candidates[i];
    //        data.remove(data.size() - 1);
    //    }
    //}
    //
    ////性能极致利用,强行排序消耗资源
    //public void sortList(List<Integer> data) {
    //    data.sort(new Comparator<Integer>() {
    //        @Override
    //        public int compare(Integer o1, Integer o2) {
    //            if (o1 > o2) {
    //                return 1;
    //            }
    //            return -1;
    //        }
    //    });
    //}




